package leet;

/**
 * Delete Columns to Make Sorted III
 * 
 * <pre>
 *  We are given an array A of N lowercase letter strings, all of the same
 * length.
 * 
 * Now, we may choose any set of deletion indices, and for each string, we
 * delete all the characters in those indices.
 *  
 * For example, if we have an array A = ["babca","bbazb"] and deletion indices
 * {0, 1, 4}, then the final array after deletions is ["bc","az"].
 * 
 * Suppose we chose a set of deletion indices D such that after deletions, the
 * final array has every element (row) in lexicographic order.
 * 
 * For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <=
 * A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <=
 * A[1][1] <= ... <= A[1][A[1].length - 1]), and so on.
 * 
 * Return the minimum possible value of D.length.
 * </pre>
 * 
 * @author zhujunbing
 * @date 2019年4月22日
 */
public class Leet0960 {

	public static void main(String[] args) {

		String[] a = { "babca", "bbazb" };
		int minDeletionSize = new Leet0960().minDeletionSize(a);

		System.out.println(minDeletionSize);
	}

	/**
	 * 类似找最长子序列，只不过是二维的
	 * 
	 * <pre>
	 * 
	 * 	 index
	 *    |
	 * b a|b c a
	 * b b|a z b
	 *    |
	 * 
	 * 
	 * </pre>
	 * 
	 * @param A
	 * @return
	 * @date 2019年4月22日
	 */
	public int minDeletionSize(String[] A) {
		int r = A[0].length();

		int[] max = new int[r];
		int m = 0;

		// 移动index
		for (int i = 0; i < r; i++) {

			// 和(0,index-1)比较
			for (int j = 0; j < i; j++) {

				// // 比较所有字符串
				// for (int k = 0; k < l; k++) {
				// // 比较字符
				// if (A[k].charAt(i) < A[k].charAt(j)) {
				// break;
				// } else if (k == l - 1) {
				// max[i] = Math.max(max[i], max[j] + 1);
				// }
				// }
				// TODO 教训,break操作这个写法在测试中耗时10ms，不用break耗时5ms

				if (compare(i, j, A)) {
					max[i] = Math.max(max[i], max[j] + 1);
				}
			}
			m = Math.max(max[i], m);
		}

		return r - m - 1;
	}

	private boolean compare(int i, int j, String[] a) {
		for (String string : a) {
			if (string.charAt(i) < string.charAt(j)) {
				return false;
			}
		}
		return true;
	}

}
